//Wed May 12 05:51:08 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int xx[] =
{ 1, 1, 0, -1, -1, -1, 0, 1 };
int yy[] =
{ 0, 1, 1, 1, 0, -1, -1, -1 };

class FuzzyLife
{
public:
	int survivingCells(vector<string> grid)
	{
		M = grid.size();
		N = grid[0].size();
		grid.insert(grid.begin(), string(N, '0'));
		grid.push_back(string(N, '0'));
		M += 2;
		for (int i = 0; i < M; i++)
		{
			grid[i] = "0" + grid[i] + "0";
		}
		N += 2;
		vector<pair<int, int> > pos;
		for (int i = 0; i < M; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (grid[i][j] == '?')
				{
					pos.push_back(make_pair(i, j));
				}
			}
		}
		int sum = 0;
		for (int n = 0; n < (1 << pos.size()); n++)
		{
			int count = 0;
			for (int k = 0; k < pos.size(); k++)
			{
				short p = ((n & (1 << k)) == 0) ? 0 : 1;
				grid[pos[k].first][pos[k].second] = '0' + p;
				//cout << grid[pos[k].first][pos[k].second] <<", ";
			}
			//cout << endl;

			for (int i = 0; i < M; i++)
			{
				for (int j = 0; j < N; j++)
				{
					cout << grid[i][j];
					if (live(i, j, grid))
						count++;
				}
				cout << endl;
			}
			cout << endl;
			sum = max(sum, count);
		}
		return sum;
	}
	bool live(int x, int y, vector<string> grid)
	{
		int count = 0;
		for (int i = 0; i < 8; i++)
		{
			int tempx = x + xx[i];
			int tempy = y + yy[i];
			if (inbound(tempx, tempy) && grid[tempx][tempy] != '0')
				count++;
		}
		if (grid[x][y] != '0' && (count == 2 || count == 3))
			return true;
		if (grid[x][y] == '0' && count == 3)
			return true;
		return false;
	}
	bool inbound(int x, int y)
	{
		if (x >= 0 && x <= M - 1 && y >= 0 && y <= N - 1)
			return true;
		return false;
	}
	int M;
	int N;
};
